// 《围棋》作者版权所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package sync

import (
	"sync/atomic"
	"unsafe"
)

// Map类似于Go Map[interface{}]interface{}，但可以安全地由多个Goroutine并发使用
// ，无需额外的锁定或协调。
// 加载、存储和删除在摊销的固定时间内运行。
// 
// 地图类型是专用的。大多数代码应该使用一个简单的Go映射，带有单独的锁定或协调，以提高类型安全性，并使其更易于维护其他不变量以及映射内容。
// 
// 映射类型针对两种常见的使用情况进行了优化：（1）当给定
// 密钥的条目只被写入一次，但被多次读取时，就像在只会增长的缓存中，
// 或（2）当多个Goroutine读取、写入和覆盖不相交的
// 密钥集的条目时。在这两种情况下，与使用单独的互斥或RWMutex的Go映射相比，使用映射可以显著减少锁
// 争用。
// 
// 零映射为空，可以使用。首次使用后不得复制地图。
type Map struct {
	mu Mutex

	// 读取包含地图内容中对
	// 并发访问安全的部分（无论是否持有mu）。
	// 
	// 读取字段本身始终可以安全加载，但必须仅与
	// mu一起存储。
	// 
	// 存储在read中的条目可以在不使用mu的情况下同时更新，但更新
	// 以前删除的条目需要将该条目复制到脏的
	// 映射中，并在保留mu的情况下取消打印。
	read atomic.Value // readOnly 

	// dirty包含需要保存mu的地图内容部分。为了确保脏映射可以快速升级到读取映射，
	// 它还包括读取映射中所有未删除的条目。
	// 
	// 删除的条目不会存储在脏映射中。
	// 干净映射中已删除的条目必须先取消打印并添加到脏映射中，然后才能将新值
	// 存储到脏映射中。
	// 
	// 如果脏映射为零，则下一次对映射的写入将通过
	// 创建干净映射的浅层副本来初始化它，忽略过时的条目。
	dirty map[any]*entry

	// misses统计自上次更新读取映射以来的加载次数，
	// 需要锁定mu以确定密钥是否存在。
	// 
	// 一旦发生足够多的未命中，足以支付复制脏的
	// 映射的成本，脏映射将升级为已读映射（处于未修改的
	// 状态），映射的下一个存储将创建新的脏拷贝。
	misses int
}

// 只读是一个原子存储在映射中的不可变结构。阅读领域。
type readOnly struct {
	m       map[any]*entry
	amended bool // 如果脏映射包含某个不在m中的密钥，则为true。
}

// expunged是一个任意指针，用于标记已从脏映射中删除的条目。
var expunged = unsafe.Pointer(new(any))

// 条目是映射中与特定密钥对应的一个插槽。
type entry struct {
	// p指向为条目存储的接口{}值。
	// 
	// 如果p==nil，则该条目已被删除，并且m.dirty==nil或
	// m.dirty[key]是e.
	// 
	// 如果p==expunged，则该条目已被删除，m.dirty！=nil，并且m.dirty中缺少条目
	// 。
	// 
	// 否则，该条目有效并记录在m.read中。m[key]如果m.dirty 
	// /！=零，以m.肮脏[钥匙]表示。
	// 
	// 一个条目可以用nil原子替换来删除：当m.dirty被
	// 下一步创建时，它将用expunged原子替换nil，并保留
	// m.dirty[key]未设置。
	// 
	// 如果
	// p！=删除。如果p==expunged，则只有在第一次设置m.dirty[key]=e之后，才能更新条目的关联值
	// 以便使用dirty 
	// 映射查找条目。
	p unsafe.Pointer // *接口{}
}

func newEntry(i any) *entry {
	return &entry{p: unsafe.Pointer(&i)}
}

// /Load返回存储在映射中的密钥值，如果不存在
// /值，则返回nil。
// ok结果指示是否在映射中找到值。
func (m *Map) Load(key any) (value any, ok bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		// 如果m.dirty在我们担任
		// 被m.mu封锁。（如果同一密钥的进一步加载不会丢失，则
		// 不值得复制此密钥的脏映射。）
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			// 无论条目是否存在，记录一次未命中：此键
			// 将采用慢速路径，直到脏映射升级为已读
			// 映射。
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if !ok {
		return nil, false
	}
	return e.load()
}

func (e *entry) load() (value any, ok bool) {
	p := atomic.LoadPointer(&e.p)
	if p == nil || p == expunged {
		return nil, false
	}
	return *(*any)(p), true
}

// 存储设置键的值。
func (m *Map) Store(key, value any) {
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok && e.tryStore(&value) {
		return
	}

	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			// 该条目之前已被删除，这意味着存在一个
			// 非零脏映射，而该条目不在其中。
			m.dirty[key] = e
		}
		e.storeLocked(&value)
	} else if e, ok := m.dirty[key]; ok {
		e.storeLocked(&value)
	} else {
		if !read.amended {
			// 我们正在向脏地图添加第一个新密钥。
			// 确保已分配，并将只读映射标记为不完整。
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
	}
	m.mu.Unlock()
}

// tryStore在条目未被删除时存储一个值。
// 
// 如果条目被删除，则tryStore返回false，并保持条目
// 不变。
func (e *entry) tryStore(i *any) bool {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == expunged {
			return false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, unsafe.Pointer(i)) {
			return true
		}
	}
}

// unpungelocked确保条目未标记为已删除。
// 
// 如果该条目之前已被删除，则必须在解锁m.mu之前将其添加到脏地图
// 中。
func (e *entry) unexpungeLocked() (wasExpunged bool) {
	return atomic.CompareAndSwapPointer(&e.p, expunged, nil)
}

// storeLocked无条件地将值存储到条目中。
// 
// 必须知道该条目不能被删除。
func (e *entry) storeLocked(i *any) {
	atomic.StorePointer(&e.p, unsafe.Pointer(i))
}

// LoadOrStore返回键（如果存在）的现有值。
// 否则，它存储并返回给定的值。
// 如果加载了值，则加载的结果为true，如果存储了值，则加载的结果为false。
func (m *Map) LoadOrStore(key, value any) (actual any, loaded bool) {
	// 如果命中率很高，请避免锁定。
	read, _ := m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		actual, loaded, ok := e.tryLoadOrStore(value)
		if ok {
			return actual, loaded
		}
	}

	m.mu.Lock()
	read, _ = m.read.Load().(readOnly)
	if e, ok := read.m[key]; ok {
		if e.unexpungeLocked() {
			m.dirty[key] = e
		}
		actual, loaded, _ = e.tryLoadOrStore(value)
	} else if e, ok := m.dirty[key]; ok {
		actual, loaded, _ = e.tryLoadOrStore(value)
		m.missLocked()
	} else {
		if !read.amended {
			// 我们正在向脏地图添加第一个新密钥。
			// 确保已分配，并将只读映射标记为不完整。
			m.dirtyLocked()
			m.read.Store(readOnly{m: read.m, amended: true})
		}
		m.dirty[key] = newEntry(value)
		actual, loaded = value, false
	}
	m.mu.Unlock()

	return actual, loaded
}

// tryLoadOrStore如果条目不是
// expunged，则自动加载或存储一个值。
// 
// 如果条目被删除，tryLoadOrStore将保持条目不变，
// 返回ok==false。
func (e *entry) tryLoadOrStore(i any) (actual any, loaded, ok bool) {
	p := atomic.LoadPointer(&e.p)
	if p == expunged {
		return nil, false, false
	}
	if p != nil {
		return *(*any)(p), true, true
	}

	// 在第一次加载后复制接口，以使此方法更易于修改
	// 以逃避分析：如果我们点击“加载”路径或条目被删除，我们
	// 不应该麻烦堆分配。
	ic := i
	for {
		if atomic.CompareAndSwapPointer(&e.p, nil, unsafe.Pointer(&ic)) {
			return i, false, true
		}
		p = atomic.LoadPointer(&e.p)
		if p == expunged {
			return nil, false, false
		}
		if p != nil {
			return *(*any)(p), true, true
		}
	}
}

// LoadAndDelete删除键的值，如果有，则返回上一个值。
// 加载的结果报告密钥是否存在。
func (m *Map) LoadAndDelete(key any) (value any, loaded bool) {
	read, _ := m.read.Load().(readOnly)
	e, ok := read.m[key]
	if !ok && read.amended {
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		e, ok = read.m[key]
		if !ok && read.amended {
			e, ok = m.dirty[key]
			delete(m.dirty, key)
			// 无论条目是否存在，记录一次未命中：此键
			// 将采用慢速路径，直到脏映射升级为已读
			// 映射。
			m.missLocked()
		}
		m.mu.Unlock()
	}
	if ok {
		return e.delete()
	}
	return nil, false
}

// Delete删除键的值。
func (m *Map) Delete(key any) {
	m.LoadAndDelete(key)
}

func (e *entry) delete() (value any, ok bool) {
	for {
		p := atomic.LoadPointer(&e.p)
		if p == nil || p == expunged {
			return nil, false
		}
		if atomic.CompareAndSwapPointer(&e.p, p, nil) {
			return *(*any)(p), true
		}
	}
}

// Range为映射中的每个键和值顺序调用f。
// 如果f返回false，range将停止迭代。
// 
// 范围不一定对应于地图的
// 内容的任何一致快照：不会多次访问任何键，但如果同时存储或删除任何键
// 的值（包括通过f），范围可能反映该键在范围调用期间的任何点的任何
// 映射。Range不
// 阻止接收器上的其他方法；甚至f本身也可以调用m上的任何方法。
// 
// 范围可以是O（N），并且映射中的元素数可以是O（N），即使f在经过恒定次数的调用后返回
// false。
func (m *Map) Range(f func(key, value any) bool) {
	// 我们需要能够迭代调用Range时已经存在的所有密钥。
	// 如果读取。如果修改的是错误的，请阅读。m在没有
	// /要求我们长期持有m.mu的情况下满足该财产。
	read, _ := m.read.Load().(readOnly)
	if read.amended {
		// m.dirty包含未读取的密钥。m、 幸运的是，Range已经是O（N）
		// （假设调用者没有提前爆发），所以对Range 
		// 的调用会摊销整个地图副本：我们可以立即推广脏副本
		// ！
		m.mu.Lock()
		read, _ = m.read.Load().(readOnly)
		if read.amended {
			read = readOnly{m: m.dirty}
			m.read.Store(read)
			m.dirty = nil
			m.misses = 0
		}
		m.mu.Unlock()
	}

	for k, e := range read.m {
		v, ok := e.load()
		if !ok {
			continue
		}
		if !f(k, v) {
			break
		}
	}
}

func (m *Map) missLocked() {
	m.misses++
	if m.misses < len(m.dirty) {
		return
	}
	m.read.Store(readOnly{m: m.dirty})
	m.dirty = nil
	m.misses = 0
}

func (m *Map) dirtyLocked() {
	if m.dirty != nil {
		return
	}

	read, _ := m.read.Load().(readOnly)
	m.dirty = make(map[any]*entry, len(read.m))
	for k, e := range read.m {
		if !e.tryExpungeLocked() {
			m.dirty[k] = e
		}
	}
}

func (e *entry) tryExpungeLocked() (isExpunged bool) {
	p := atomic.LoadPointer(&e.p)
	for p == nil {
		if atomic.CompareAndSwapPointer(&e.p, nil, expunged) {
			return true
		}
		p = atomic.LoadPointer(&e.p)
	}
	return p == expunged
}
